home *** CD-ROM | disk | FTP | other *** search
/ MacTech 1 to 12 / MacTech-vol-1-12.toast / Source / MacTech® Magazine / Volume 10 - 1994 / 10.04 Apr 94 / Programmers' Challenge / anagram.c
Encoding:
C/C++ Source or Header  |  1994-02-13  |  8.8 KB  |  316 lines  |  [TEXT/KAHL]
  1. /*
  2.    Anagram Programmer's Challenge
  3.    
  4.    by Larry Landry
  5.  
  6.    This implementation uses a large amount of memory to
  7.    optimize the CPU utilization.  To guarantee that we
  8.    have enough memory for all matching words, we actually
  9.    allocate an array of pointers for 30,000 words.  Since
  10.    the rules stated that there would be about 20,000 words
  11.    in the dictionary, even if every word matched, we would
  12.    still have enough storage.  In reality this number
  13.    could probably be less than 1-200 for all but the most
  14.    rare of scenarios.
  15.  
  16.    The basic algorithm is:
  17.    1) Convert the input string into a table of counts for
  18.    each character from a-z.  So "sammy" would have a
  19.    count of 2 for "m" and 1 for each of "s", "a", and "y".
  20.    This makes testing for the presence of a character
  21.    as simple as checking and indexed value in an array.
  22.    2) Parse through the dictionary and find the words that
  23.    can be composed of some portion of characters from
  24.    the input characters.  Build a list of pointers to
  25.    each word.  The number of words in this list will
  26.    be in the tens instead of thousands.
  27.    3) Recursively process the words in this list and find
  28.    strings of words that use up all of the characters.
  29.    For each matching sequence, output the words to
  30.    the file.
  31.  
  32.    The processing requrired by this algorithm is then
  33.    D * C1 + M * log2(M) * C2
  34.    where
  35.    D = size of input dictionary
  36.    M = number of matching words
  37.    C1 & C2 are constants
  38.    This algorithm works very well for cases where there are
  39.    few words that match the input letters.  The worst case
  40.    scenario where all words can be made from the input letters
  41.    will still take a very long time.  I expect that matching
  42.    words will typically be less than 100.
  43.  
  44. */
  45.  
  46. #include   <stdio.h>
  47.  
  48. typedef unsigned char   uchar;
  49. typedef unsigned short ushort;
  50. typedef unsigned long  ulong;
  51.  
  52. #define MAX_WORDS   30000L
  53. #define OUTPUT_BUFFER_SIZE  10000L
  54. #define RETURN  '\n'
  55.  
  56. typedef struct {
  57.    char*fWordStart;
  58.    short   fWordLength;
  59. } WordLoc;
  60.  
  61. /* Usage counts for each character
  62. (only indexes 'a' to 'z' are actually used) */
  63.  
  64. typedef uchar   CharData[256];
  65.  
  66. unsigned long Anagram(Str255 inputText, FILE *wordList,
  67.    FILE *outputFile);
  68.  
  69. ulong findInputWords(register char *wordBuffer,
  70.    WordLoc *validWords);
  71. ulong findAnagrams(short numValidChars, ulong wordCount,
  72.    WordLoc *validWords, short prevWordCount);
  73.  
  74.  
  75. /* I use some global variables here to avoid passing them
  76. down into the recursive routine findAnagrams().  These values
  77. are constant once findAnagrams() is called. */
  78.  
  79. char   gOutputBuffer[OUTPUT_BUFFER_SIZE];
  80. char   *gOutputBufferEnd = gOutputBuffer +
  81.    OUTPUT_BUFFER_SIZE - 512;
  82. char   *gOutputPtr;
  83. CharData   gValidChars;
  84. WordLoc    *gWordsInUse[255];
  85. FILE   *gOutputFile;
  86.  
  87.  
  88. unsigned long Anagram(Str255 inputText, FILE *wordList,
  89.    FILE *outputFile)
  90. {
  91.    fpos_t  wordBufferLength;
  92.    char*wordBuffer;
  93.    short   index;
  94.    short   numValidChars;
  95.    WordLoc validWords[MAX_WORDS];
  96.    char ch;
  97.    ulong   wordCount;
  98.  
  99.    gOutputFile = outputFile;
  100.    gOutputPtr = gOutputBuffer;
  101.  
  102.    /* To save on file I/O time, read the whole file
  103.    all at once.  First, find the length of the file
  104.    by seeking the end and finding the file pos.
  105.    Then allocate a buffer of that size, plus 2 bytes
  106.    (for a return and NULL char) and read the data
  107.    into it.  Finally put the return and NULL char
  108.    at the end. */
  109.  
  110.    fseek(wordList, 0L, SEEK_END);
  111.    fgetpos(wordList, &wordBufferLength);
  112.    wordBuffer = (char*) NewPtr((Size) wordBufferLength + 2);
  113.    if (wordBuffer == NULL)
  114.    return 0L;  /* real error handling here */
  115.    rewind(wordList);
  116.    fread(wordBuffer, (size_t) 1,
  117.    (size_t) wordBufferLength, wordList);
  118.    if (wordBuffer[wordBufferLength-1] != RETURN)
  119.    wordBuffer[wordBufferLength++] = RETURN;
  120.    wordBuffer[wordBufferLength] = '\0';
  121.  
  122.    /* To save time ruling out words, we build a
  123.    list of the valid characters in the words.  We start
  124.    with no valid characters. */
  125.    for (index='a'; index<'z'; index++)
  126.    gValidChars[index] = 0;
  127.  
  128.    /* Now build the list of valid characters.
  129.    Each array entry will be a count of how
  130.    many times that character is present. */
  131.  
  132.    numValidChars = *inputText++;
  133.    for (index=numValidChars; index>0; index--)
  134.    if ((ch = *inputText++) != ' ')
  135.    gValidChars[ch]++;
  136.    else
  137.    numValidChars--;
  138.  
  139.    /* Find the list of words that can be made up from the
  140.    letters in the input word */
  141.  
  142.    wordCount = findInputWords(wordBuffer, &validWords[MAX_WORDS-1]);
  143.  
  144.    /* Now find the list of full anagrams that can be
  145.    created from these words */
  146.  
  147.    wordCount = findAnagrams(numValidChars, wordCount,
  148.    &validWords[MAX_WORDS-wordCount], 0);
  149.  
  150.    /* Write the results to the output */
  151.    *gOutputPtr = 0;/* Terminate the string */
  152.    fprintf(outputFile, gOutputBuffer);
  153.  
  154.    DisposPtr(wordBuffer);
  155.  
  156.    return wordCount;
  157. } /* Anagram */
  158.  
  159.  
  160. ulong findInputWords(register char *wordBuffer,
  161.    WordLoc *validWords)
  162. {
  163.    char*saveStart = wordBuffer;
  164.    ulong   numberWords = 0;
  165.    char ch;
  166.  
  167.    while (*wordBuffer)
  168.    {
  169.    ch = *wordBuffer++;
  170.    if (ch == RETURN)
  171.    {
  172.    /* Record this entry as a valid word */
  173.    numberWords++;
  174.    validWords->fWordStart = saveStart;
  175.    validWords->fWordLength = (short)(wordBuffer -
  176.    saveStart - 1);
  177.    validWords--;
  178.  
  179.    wordBuffer--;
  180.    while (saveStart < wordBuffer)
  181.    gValidChars[*saveStart++]++;
  182.  
  183.    /* Save the new start of word pointer */
  184.    saveStart = ++wordBuffer;
  185.    } else if (gValidChars[ch])
  186.    gValidChars[ch]--;
  187.    else
  188.    {
  189.    /* This word didn't match so reset and go to the
  190.    next word */
  191.  
  192.    wordBuffer--;
  193.    while (saveStart < wordBuffer)
  194.    gValidChars[*saveStart++]++;
  195.    while (*wordBuffer++ != RETURN)
  196.    ;
  197.  
  198.    /* Save the new start of word pointer */
  199.    saveStart = wordBuffer;
  200.    } /* else */
  201.    } /* while */
  202.  
  203.    return numberWords;
  204. } /* findInputWords */
  205.  
  206.  
  207. ulong findAnagrams(short numValidChars, ulong wordCount,
  208.    WordLoc *validWords, short prevWordCount)
  209. {
  210.    ulong   wordIndex;
  211.    ulong   usedIndex;
  212.    short   chIndex;
  213.    ulong   matchCount = 0;
  214.    Boolean wordFits;
  215.    char ch;
  216.    char*tempPtr;
  217.    WordLoc *theWord;
  218.  
  219.    /* Try each word we have against the list of characters. */
  220.  
  221.    for (wordIndex=0; wordIndex<wordCount; wordIndex++)
  222.    {
  223.    /* If there aren't enough characters left,
  224.    it can't be a match */
  225.  
  226.    if (validWords->fWordLength <= numValidChars)
  227.    {
  228.    /* Go through the chars in this word testing to
  229.    make sure that there is at least one of each char
  230.    available */
  231.    wordFits = TRUE;
  232.    for (chIndex=0; chIndex<validWords->fWordLength; chIndex++)
  233.    {
  234.    ch = validWords->fWordStart[chIndex];
  235.    if (gValidChars[ch])
  236.    gValidChars[ch]--;
  237.    else
  238.    {
  239.    /* Found an unavailable character, so this
  240.    can't be part of the anagram.  Reset the
  241.    character usage array and go to the next
  242.    word. */
  243.  
  244.    wordFits = FALSE;
  245.    while (--chIndex >= 0)
  246.    gValidChars[validWords->fWordStart[chIndex]]++;
  247.    break;  /* get out of the for loop */
  248.    } /* else */
  249.    } /* for */
  250.  
  251.    if (wordFits)
  252.    {
  253.    /* This word fit, so see if it uses all the characters.
  254.    If so, then we have found an anagram.  Output the
  255.    anagram and increment the anagram count. */
  256.  
  257.    if (validWords->fWordLength == numValidChars)
  258.    {
  259.    matchCount++;
  260.    /* Copy the previous words for this anagram
  261.    separated by spaces. */
  262.    for (usedIndex=0; usedIndex<prevWordCount; usedIndex++)
  263.    {
  264.    theWord = gWordsInUse[usedIndex];
  265.    memcpy(gOutputPtr, theWord->fWordStart,
  266.    (size_t) theWord->fWordLength);
  267.    gOutputPtr += theWord->fWordLength;
  268.    *gOutputPtr++ = ' ';
  269.    } /* for */
  270.  
  271.    /* Now copy this new word and a return character */
  272.    memcpy(gOutputPtr, validWords->fWordStart,
  273.    (size_t) validWords->fWordLength);
  274.    gOutputPtr += validWords->fWordLength;
  275.    *gOutputPtr++ = RETURN;
  276.  
  277.    /* To ensure that we don't overrun the output buffer
  278.    check against the end of the buffer.  If the end
  279.    pointer has been passed, write the data to the file
  280.    and reset the output pointer to the beginning of
  281.    the buffer. */
  282.  
  283.    if (gOutputPtr > gOutputBufferEnd)
  284.    {
  285.    *gOutputPtr = 0;/* Terminate the string */
  286.    fprintf(gOutputFile, gOutputBuffer);
  287.    gOutputPtr = gOutputBuffer;
  288.    } /* if */
  289.    }
  290.    else
  291.    {
  292.    /* This word did fit, but didn't use all of the
  293.    characters so add it to the list of previous words
  294.    in the anagram and then call this procedure
  295.    recursively to find if there are more words that
  296.    can be added to make an anagram with this base. */
  297.  
  298.    gWordsInUse[prevWordCount] = validWords;
  299.    matchCount += findAnagrams(
  300.    numValidChars - validWords->fWordLength,
  301.    wordCount - wordIndex, validWords,
  302.    prevWordCount + 1);
  303.    } /* else */
  304.  
  305.    /* Now undo the characters we took out of the validChar array */
  306.    for (chIndex=0; chIndex<validWords->fWordLength; chIndex++)
  307.    gValidChars[validWords->fWordStart[chIndex]]++;
  308.    } /* if */
  309.    } /* if */
  310.  
  311.    validWords++;
  312.    } /* for */
  313.  
  314.    return matchCount;
  315. } /* findAnagrams */
  316.